﻿#pragma once
#include <ctime>
#include <iostream>
#include <vector>
#include <thread>
#include <cassert>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <atomic>
#include <cstring>



#ifdef _WIN64
#include <Windows.h>	
using PAGE_ID = unsigned long long;
#define DEEP 64
#elif defined _WIN32
#include <Windows.h>
using PAGE_ID = size_t;
#define DEEP 32
#else
#include <unistd.h>
#include <sys/mman.h>
#define DEEP 32
using PAGE_ID = unsigned long long;
#endif

using std::cin;
using std::cout;
using std::endl;

// thread cache 和 central cache⾃由链表哈希桶的表⼤⼩
static const size_t NFREELISTS = 208;

// ⼤于MAX_BYTES，就直接找page cache或者系统堆申请
static const size_t MAX_BYTES = 256 * 1024;

// page cache 管理span list哈希表⼤⼩
static const size_t NPAGES = 129;

// ⻚⼤⼩转换偏移, 即⼀⻚定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13;

////申请空间接口
//inline static void* SystemAlloc(size_t kpage) {
//#ifdef _WIN32
//	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE,
//		PAGE_READWRITE);
//#else
//	// linux下brk mmap相关接口
//#endif
//
//	if (ptr == nullptr) {
//		throw std::bad_alloc();
//	}
//	return ptr;
//}
// 
// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT , MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
	void* ptr = mmap(nullptr,
		kpage << PAGE_SHIFT,
		PROT_READ | PROT_WRITE,
		MAP_PRIVATE | MAP_ANONYMOUS,
		-1, 0);

#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}


inline static void SystemFree(void* ptr, int kpage = 0)
{
#ifdef _WIN32
	
		VirtualFree(ptr, 0, MEM_RELEASE);
#else
// sbrk unmmap等
	munmap(ptr, kpage << PAGE_SHIFT); // 必须传递正确长度[4](@ref)
#endif
}


//管理对象的自由链表
class FreeList {
public:
	//头插
	void Push(void* obj);
	//头删
	void* Pop();
	//判断_freelist是否为空
	bool Empty();
	//将一连串块接续挂在自由链表下 头插
	void PushRange(void* start, void* end, size_t n);

	//将一连串的内存块从freelist里取出来
	void PopRange(void*& start, void*& end, size_t n);
	
	size_t& MaxSize() { return _maxSize; }
	size_t Size() { return _size; }
private:
	void* _freeList = nullptr;

	//存储每次向CentralCache里的Span中的自由链表获取多少个块
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 获取内存对象中存储的头4 or 8字节值，即链接的下⼀个对象的地址
static inline void*& NextObj(void* obj) {
	return *((void**)obj);
}

//管理多个连续页的大块内存
class Span {

public:

	//Span开始的页号地址, systemAlloc申请的地址右移8k
	PAGE_ID _pageId = 0;
	//从开始页的长度
	size_t _n = 0;

	//前一个span
	Span* _pre = nullptr;
	//后一个Span
	Span* _next = nullptr;

	//切好的小块内存, 分配给 threadCache的计数
	size_t _useCount = 0;

	//切好的小块内存的自由链表
	void* _freeList = nullptr;

	//该span是否被使用
	bool _isUsed = false;

	//自由链表下每块内存块的大小
	size_t _size = 0;
};

//带头双向循环链表
class SpanList {
public:
	SpanList() : _head(new Span()) {
		_head->_pre = _head;
		_head->_next = _head;
	}

	//在pos前任意插入操作统一
	void Insert(Span* pos, Span* newSpan) {
		assert(pos);
		assert(newSpan);
		Span* pre = pos->_pre;
		pre->_next = newSpan;
		newSpan->_pre = pre;
		newSpan->_next = pos;
		pos->_pre = newSpan;
	}
	//
	void Erase(Span* pos) {
		assert(pos);
		assert(pos != _head);
		Span* pre = pos->_pre;
		Span* next = pos->_next;
		pre->_next = next;
		next->_pre = pre;

	}
	//头插
	void FrontPush(Span* span) {
		Insert(_head->_next, span);
	}

	//头删
	Span* FrontPop() {
		Span* ret = _head->_next;
		Erase(ret);
		return ret;
	}

	Span* Begin() {
		return _head->_next;
	}
	Span* End() {
		return _head;
	}

	bool Empty() {
		return _head->_next == _head;
	}
	~SpanList() { delete _head; }

private:
	Span* _head;
	

public:
	std::mutex mtx;
};

//管理对齐和映射关系
class SizeClass {
public:
	//计算自由链表块大小
	static size_t _RoundUp(size_t bytes, size_t align);
	static size_t RoundUp(size_t bytes);
	//计算自由链表桶下标
	static size_t _Index(size_t bytes, size_t align_shift);
	static size_t Index(size_t bytes);

	// 一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size);

	// 计算⼀次向系统获取⼏个⻚
// 单个对象 8byte
// ...
// 单个对象 256KB
	static size_t NumMovePage(size_t size);

};
